/*
 * @time : 2022/5
 * @author : liyajun
 * @homepage : moreac.top
 */
#include <bits/stdc++.h>

const int N = 1e6 + 10;

using namespace std;


int a[N],b[N],f[N],n,m,t[N];
void merge(int l,int r) {
	if(l >= r) return ;
	int mid1 = l + (r - l) / 3,mid2 = r - (r - l) / 3;
	merge(l,mid1);
	merge(mid1 + 1,mid2);
	merge(mid2 + 1,r);
	int p = l,p1 = l,p2 = mid1 + 1,p3 = mid2 + 1;
	while(p1 <= mid1 && p2 <= mid2 && p3 <= r) {
		if(a[p1] <= a[p2] && a[p1] <= a[p3])
			t[p++] = a[p1++];
		else if(a[p2] <= a[p1] && a[p2] <= a[p3])
			t[p++] = a[p2++];
		else
			t[p++] = a[p3++];
	}
	
	while(p1 <= mid1 && p2 <= mid2) {
		if(a[p1] < a[p2]) t[p++] = a[p1++];
		else t[p++] = a[p2++];
	}
	while(p1 <= mid1 && p3 <= r) {
		if(a[p1] < a[p3]) t[p++] = a[p1++];
		else t[p++] = a[p3++];
	}
	while(p2 <= mid2 && p3 <= r) {
		if(a[p2] < a[p3]) t[p++] = a[p2++];
		else t[p++] = a[p3++];
	}
	
	while(p1 <= mid1) t[p++] = a[p1++];
	while(p2 <= mid2) t[p++] = a[p2++];
	while(p3 <= r) t[p++] = a[p3++];
	
	for(int i = r;i>=l;i--) a[i] = t[i];
}

void pr()
{
	for(int i = 1;i <= n;i++)cout<<a[i]<<" ";
	cout<<endl;
}
void slove()
{
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> a[i];
	pr();
	merge(1,n);
	pr();
}
int main() {
	int T = 1;
	//cin >> T;
	while(T--)slove();



	return 0;
}

